1400G - Mercenaries - CodeForces Solution

/// muthafucka you deserve to die
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

#define pb push_back
#define F first
#define S second
#define f(i, a, b)  for(int i = a; i < b; i++)
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define mp(x, y) make_pair(x,y)
#define popCnt(x) (__builtin_popcountll(x))
//#define int ll

using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;

const int N = 3e5 + 5, LG = 19, MOD = (119 << 23) + 1, MOD2 = 1e9 + 7;
const long double PI = acos(-1);
const long double EPS = 1e-7;
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
const int dx[] = {-1, 1, -1, 1};
const int dy[] = {1, -1, -1, 1};
int n, m;
int l[N], r[N];
ll F[N], iF[N];

ll fast(ll b, ll e) {
    ll res = 1;
    for (; e; e >>= 1, b = b * b % MOD)
        if (e & 1)
            res = res * b % MOD;
    return res;
}

void init() {
    F[0] = 1;
    f(i, 1, N)F[i] = F[i - 1] * i % MOD;
    iF[N - 1] = fast(F[N - 1], MOD - 2);
    for (int i = N - 2; i >= 0; --i)
        iF[i] = iF[i + 1] * (i + 1) % MOD;
}

int C(int n, int k) {
    if (k > n || k < 0)
        return 0;
    return iF[k] * F[n] % MOD * iF[n - k] % MOD;
}

vector<int> adj[N];
vector<int> special;
bool have[44];
int cnt[N];
vector<ii> add[N];
vector<ii> del[N];
bool vis[N];
int dp[22], nxt[22];

void bt(int index, int lftRange, int rightRange, int vecIndex, int cnt = 0) {
    if (lftRange > rightRange)
        return;
    if (index == special.size()) {
        if (cnt) {
            add[lftRange].push_back({cnt, vecIndex});
            del[rightRange].push_back({cnt, vecIndex});
        }
        return;
    }
    bt(index + 1, lftRange, rightRange, vecIndex, cnt);
    bool ok = true;
    for (auto x: adj[special[index]])
        ok &= (!have[x]);
    if (ok) {
        have[special[index]] = true;
        bt(index + 1, max(lftRange, l[special[index]]), min(rightRange, r[special[index]]), vecIndex, cnt + 1);
        have[special[index]] = false;
    }
}

void dfs(int node) {
    special.push_back(node);
    vis[node] = true;
    for (auto x: adj[node])
        if (!vis[x]) {
            dfs(x);
        }
}

int vals[22][22];

void doWork() {
    init();
    cin >> n >> m;
    f(i, 1, n + 1) {
        cin >> l[i] >> r[i];
    }
    set<int> st;
    f(i, 0, m) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
        st.insert(u);
        st.insert(v);
    }

    int tot = 0;
    for (auto x: st)
        if (!vis[x]) {
            special.clear();
            dfs(x);
            bt(0, 0, n, tot++);
        }
    f(i, 1, n + 1)if (!st.count(i))cnt[l[i]] += 1, cnt[r[i] + 1] -= 1;
    int ans = 0;
    f(i, 1, n + 1) {
        cnt[i] += cnt[i - 1];
        for (auto [x, y]: add[i])vals[y][x] += 1;
        ::memset(dp, 0, sizeof dp);
        dp[0] = 1;
        for (int j = 0; j < tot; j++) {
            memset(nxt, 0, sizeof nxt);
            for (int k = 1; k <= 20; k++)
                if (vals[j][k]) {
                    for (int x = 0; x + k <= 20; x++) {
                        nxt[x + k] = (nxt[x + k] + 1ll * dp[x] * vals[j][k]) % MOD;
                    }
                }
            f(k, 0, 21) {
                if ((dp[k] += nxt[k]) >= MOD)
                    dp[k] -= MOD;
            }
        }
        for (int j = 0; j <= min(20, i); j++)
            if (dp[j]) {
                ans = (ans + 1ll * dp[j] * C(cnt[i], i - j)) % MOD;
            }

        for (auto [x, y]: del[i])vals[y][x] -= 1;
    }

    cout << ans << '\n';


}

int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE
    init();
    int t = 1;
//    cin >> t;
    while (t--) {
        doWork();
    }
    return 0;
}